package com.ls.linkList;
/**
 * @program: dataStructure
 * @author: lishun
 * @create: 2021-11-26 13:56
 **/
import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;
import java.util.Objects;

/**
 * 双向链表
 */
@NoArgsConstructor
@AllArgsConstructor
@Data
@Builder
public class DoubleLinkList {
    DoubleLinkList pre;
    DoubleLinkList next;
    int data;


    public static void main(String[] args) {
        DoubleLinkList linkList = new DoubleLinkList(1);
//        linkList.show();
        for (int i = 2;i<=5;i++){
            linkList.addBySize(new DoubleLinkList(i));
        }

//        System.out.println(linkList.length());
        linkList.show();
//        linkList.insert(5,new DoubleLinkList(33));
//        System.out.println();
//        linkList.show();
        System.out.println("删除测试");
//        linkList.delete(2);
//        linkList.show();
        System.out.println();
        recShow(linkList);

    }

    public DoubleLinkList(int data) {
        this.data = data;
    }

    /**
     * 遍历
     */
    public void show(){
        DoubleLinkList current = this;
        while (current.next!=null){
            System.out.print(current.data+"-->");
            current = current.getNext();
        }
        System.out.print(current.data+"-->null");
    }
    /**
     * 尾部添加
     */
    public void addLast(DoubleLinkList doubleLinkList){
        DoubleLinkList current = this;
        // 找到尾部
        while (current.getNext()!=null){
            current=current.getNext();
        }
        doubleLinkList.setPre(current);
        current.setNext(doubleLinkList);
    }
    // 求长度
    public int length(){
        DoubleLinkList current = this;
        int length = 1;
        while (current.getNext()!=null){
            length++;
            current = current.getNext();
        }
        return length;
    }
    /**
     * 头部添加
     */
    public void addTop(){
        // 一样的，不同的就是对象要换，或者搞个头指针
    }
    /**
     * 中间添加
     */
    public void insert(int position,DoubleLinkList doubleLinkList){

        if (position< 2|| position>this.length()||Objects.isNull(doubleLinkList)){
            throw new RuntimeException();
        }
        DoubleLinkList current = this;
        // 遍历到插入位置
        int count = 1;
        while (count<position){
            current = current.getNext();
            count++;
        }
        doubleLinkList.setPre(current.getPre());
        current.getPre().setNext(doubleLinkList);
        current.setPre(doubleLinkList);
        doubleLinkList.setNext(current);
    }
    /**
     * 递归展示
     */
    public static void recShow(DoubleLinkList doubleLinkList){
        if (doubleLinkList.getNext()==null){
            System.out.println(doubleLinkList.data);
            System.out.println(doubleLinkList.pre.data);
            return;
        }
        recShow(doubleLinkList.getNext());
       if (doubleLinkList.pre!=null){
           System.out.println(doubleLinkList.pre.data);
       }
    }
    /**
     * 删除
     */
    public void delete(int position){
        // `头部数据不删除
        if (position< 2|| position>this.length()){
            throw new RuntimeException("删除位置不合理");
        }
        // 遍历到删除的位置
        DoubleLinkList current = this;
        int count = 1;
        while (count<position){
            current = current.getNext();
            count++;
        }
        // 中间位置？最后一个位置
        current.getPre().setNext(current.getNext());
        if (current.getNext() != null) {
            current.getNext().setPre(current.getPre());
        }
    }
    /**
     *
     * 按大小添加
     */
    // TODO 没做
    public void addBySize(DoubleLinkList doubleLinkList){
        DoubleLinkList current = this;
        // 遍历到大于等于
        while (current !=null){
            if (current.data<doubleLinkList.data){
                break;
            }
            current=current.getNext();
        }
        // 插入到这个之后
        current.getPre().setNext(current.getNext());
        if (current.getNext() != null) {
            current.getNext().setPre(current.getPre());
        }
    }
}
